#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TABLE_SIZE 10 // 哈希表大小

// 哈希表结点结构
struct HashNode
{
    int key;               // 键
    int value;             // 值
    struct HashNode *next; // 链表指针（未使用，因为无冲突）
};

// 哈希表结构
struct HashTable
{
    struct HashNode **buckets; // 桶数组
    int size;                  // 表大小
};

// 创建哈希表
struct HashTable *createHashTable(int size)
{
    struct HashTable *table = (struct HashTable *)malloc(sizeof(struct HashTable));
    table->size = size;
    table->buckets = (struct HashNode **)malloc(size * sizeof(struct HashNode *));

    // 初始化所有桶为空
    for (int i = 0; i < size; i++)
    {
        table->buckets[i] = NULL;
    }

    return table;
}

// 1. 除留余数法哈希函数
int hashModulo(int key)
{
    return key % TABLE_SIZE;
}

// 2. 直接定址法哈希函数（h(key) = a * key + b）
int hashDirect(int key)
{
    int a = 3; // 系数
    int b = 1; // 常数项
    return (a * key + b) % TABLE_SIZE;
}

// 3. 数字分析法哈希函数（取关键字的中间数字）
int hashDigitAnalysis(int key)
{
    // 将key视为3位数字（例如123）
    int hundreds = key / 100;   // 百位
    int tens = (key / 10) % 10; // 十位
    int units = key % 10;       // 个位

    // 使用十位数字作为哈希值
    return tens % TABLE_SIZE;
}

// 4. 平方取中法哈希函数
int hashMidSquare(int key)
{
    long square = (long)key * key; // 计算平方
    int digits = 0;
    long temp = square;

    // 计算数字位数
    while (temp != 0)
    {
        digits++;
        temp /= 10;
    }

    // 取中间两位数字
    int middle = (square / (long)pow(10, digits / 2 - 1)) % 100;
    return middle % TABLE_SIZE;
}

// 向哈希表插入键值对（无冲突）
void insert(struct HashTable *table, int key, int value, int (*hashFunc)(int))
{
    // 计算哈希值
    int index = hashFunc(key);

    // 创建新结点
    struct HashNode *newNode = (struct HashNode *)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;

    // 直接插入（无冲突处理）
    table->buckets[index] = newNode;
}

// 打印哈希表
void printHashTable(struct HashTable *table, const char *method)
{
    printf("\nHash Table using %s:\n", method);
    printf("Index\tKey\tValue\n");
    printf("--------------------\n");

    for (int i = 0; i < table->size; i++)
    {
        if (table->buckets[i] != NULL)
        {
            printf("%d\t%d\t%d\n", i, table->buckets[i]->key, table->buckets[i]->value);
        }
    }
}

// 主函数测试
int main()
{
    // 创建四个哈希表，使用不同的哈希函数
    struct HashTable *tableModulo = createHashTable(TABLE_SIZE);
    struct HashTable *tableDirect = createHashTable(TABLE_SIZE);
    struct HashTable *tableDigit = createHashTable(TABLE_SIZE);
    struct HashTable *tableMidSquare = createHashTable(TABLE_SIZE);

    // 插入无冲突的键值对（为每个哈希函数选择无冲突的键）

    // 除留余数法：键选择为10, 11, 12...（不会冲突）
    insert(tableModulo, 10, 100, hashModulo);
    insert(tableModulo, 11, 110, hashModulo);
    insert(tableModulo, 12, 120, hashModulo);

    // 直接定址法：键选择为1, 2, 3...（不会冲突）
    insert(tableDirect, 1, 100, hashDirect);
    insert(tableDirect, 2, 200, hashDirect);
    insert(tableDirect, 3, 300, hashDirect);

    // 数字分析法：键选择为123, 456, 789（十位数字不同）
    insert(tableDigit, 123, 100, hashDigitAnalysis);
    insert(tableDigit, 456, 200, hashDigitAnalysis);
    insert(tableDigit, 789, 300, hashDigitAnalysis);

    // 平方取中法：键选择为10, 20, 30（平方后中间位不同）
    insert(tableMidSquare, 10, 100, hashMidSquare);
    insert(tableMidSquare, 20, 200, hashMidSquare);
    insert(tableMidSquare, 30, 300, hashMidSquare);

    // 打印所有哈希表
    printHashTable(tableModulo, "Modulo Division Method");
    printHashTable(tableDirect, "Direct Addressing Method");
    printHashTable(tableDigit, "Digit Analysis Method");
    printHashTable(tableMidSquare, "Mid-Square Method");

    return 0;
}